package chapter02;

import java.util.ArrayList;
import java.util.List;

public class GenerateTrees95 {
    /**
     * 回溯法
     * process(start,end) 当前来到子树根节点 取值为[start,end] 返回子树根节点集合
     * 假设 当前根节点为i 左子树可以取值[start.i-1] 右子树可以取值[i+1,end]
     * 递归出口
     * path=new List();
     *  1).start>end
     *      path.add(null)
     *      return path
     *  2).枚举根节点
     *      i->[start,end]
     *          leftRoot=process(start,i-1) 左子树根节点
     *          rightRoot=process(i+1,end) 右子树根节点
     *          for leftNode:leftRoot 左右子树根节点笛卡尔积
     *              for rightNode:rightRoot
     *                  root=new TreeNode(i)
     *                  root.left=leftNode
     *                  root.right=rightNode
     *                  path.add(root)  子树根节点加入集合
     *      return path
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<TreeNode> generateTrees(int n) {
        return process(1,n);
    }

    public List<TreeNode> process(int start,int end){
        List<TreeNode> path=new ArrayList<>();
        if(start>end){
            path.add(null);
            return path;
        }
        for(int num=start;num<=end;num++){
            List<TreeNode> leftRoot=process(start,num-1);
            List<TreeNode> rightRoot=process(num+1,end);
            for(TreeNode leftNode:leftRoot){
                for(TreeNode rightNode:rightRoot){
                    TreeNode root=new TreeNode(num);
                    root.left=leftNode;
                    root.right=rightNode;
                    path.add(root);
                }
            }
        }
        return path;
    }

//    public static void main(String[] args) {
//        System.out.println(new GenerateTrees95().generateTrees(3));
//    }
}
